package leet;

import java.util.ArrayList;
import java.util.List;

/**
 * @author longzj
 */
class LongestPalindrome {

    public static void main(String[] args) {
        LongestPalindrome palindrome = new LongestPalindrome();

        String test = "abcdeffe";
        String str = palindrome.dynamicPalindrome(test);
        System.out.println("str-->>" + str);
    }

    private String longestPalindrome(String s) {
        char[] charArray = s.toCharArray();
        List<Character> cacheStack = new ArrayList<>();
        String maxStr = "";
        int max = 0;
        int length = charArray.length;
        for (int pos = 0; pos < length; pos++) {
            char firstChar = charArray[pos];
            cacheStack.clear();
            int subLength = length;
            int lastPos = subLength - 1;
            for (int index = pos; index < subLength; index++) {
                if (index >= lastPos) {
                    boolean isEqual = index == lastPos;
                    int size = cacheStack.size() * 2;
                    if (isEqual) {
                        size += 1;
                    }
                    if (size > max) {
                        maxStr = getMaxStr(cacheStack, charArray[index], isEqual);
                        max = size;
                    }

                    break;
                }
                char headerChar = charArray[index];
                char footerChar = charArray[lastPos];
                if (headerChar == footerChar) {
                    cacheStack.add(footerChar);
                    lastPos--;
                } else {
                    index = pos - 1;
                    subLength -= 1;
                    lastPos = subLength - 1;
                    cacheStack.clear();
                }
            }
        }
        if (max == 0 && length != 0) {
            maxStr = String.valueOf(charArray[0]);
        }
        return maxStr;
    }

    private String dynamicPalindrome(String input) {
        String result = "";
        int inputLen = input.length();
        for (int index = 0; index < input.length(); index++) {
            char currentChar = input.charAt(index);
            int left = index - 1;
            int right = index + 1;
            if (right < input.length() && currentChar == input.charAt(right)) {
                result = getString(left, right + 1, input, result);
            }
            result = getString(left, right, input, result);
            if (result.length() == inputLen) {
                break;
            }
        }
        return result;
    }

    private String getString(int left, int right, String input, String result) {
        char leftChar;
        char rightChar;
        int len = result.length();
        int inputLen = input.length();
        while (left >= 0 && right < inputLen) {
            leftChar = input.charAt(left);
            rightChar = input.charAt(right);
            if (leftChar != rightChar) {
                break;
            }
            left--;
            right++;
        }
        left += 1;
        int tmp = right - left;
        if (tmp > len) {
            result = input.substring(left, right);
        }
        return result;
    }

    private String getMaxStr(List<Character> list, char middleChar, boolean isMedian) {
        StringBuilder builder = new StringBuilder();
        int size = list.size();
        for (char c : list) {
            builder.append(c);
        }
        if (isMedian) {
            builder.append(middleChar);
        }
        for (int index = size - 1; index >= 0; index--) {
            builder.append(list.get(index));
        }
        return builder.toString();
    }
}
